package leetcode_day._2022._202201._2131;

import java.util.*;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/1/24 12:46
 * 到达目的地的第二短时间
 * 算法：广度优先搜索
 * 先得到第二短时间的路径，再根据路径计算时间
 * 要想得到第二短时间的路径，要先得到最短时间的路径
 */
public class _24_2045 {

    public int secondMinimum(int n, int[][] edges, int time, int change) {
        // 路径
        List<Integer>[] graph = new List[n + 1];
        // path[n][0] --- 1 到 n 的最短路径, path[n][1] --- 1 到 n 的次短路径
        int[][] path = new int[n + 1][2];
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
            Arrays.fill(path[i], Integer.MAX_VALUE);
        }
        for (int[] edge : edges) {
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }
        Deque<int[]> queue = new ArrayDeque<>();
        queue.addLast(new int[]{1, 0});
        while (path[n][1] == Integer.MAX_VALUE) {
            int[] poll = queue.poll();
            int cur = poll[0], step = poll[1];
            for (Integer next : graph[cur]) {
                if (step + 1 < path[next][0]) {
                    queue.addLast(new int[]{next, step + 1});
                    path[next][0] = step + 1;
                } else if (step + 1 > path[next][0] && step + 1 < path[next][1]) {
                    queue.addLast(new int[]{next, step + 1});
                    path[next][1] = step + 1;
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < path[n][1]; i++) {
            int a = ans / change, b = ans % change;
            int wait = a % 2 == 0 ? 0 : change - b;
            ans += time + wait;
        }
        return ans;
    }

}
